The disclosure generally relates to the field of data storage, and more particularly to using a tree-based data structure to map logical block addresses to physical block addresses on a storage device.
An increasing amount of data is being stored. Although the per unit cost associated with storing data has declined over time, the total costs for storage has increased for many corporate entities because of the increase in volume of stored data.
In response, manufacturers of data storage drives (e.g., magnetic hard disk drive) have increased data storage capacity by using various techniques, including increasing the number of platters and the density of tracks and sectors on one or both surfaces of the platters. A platter is commonly a circular disk having one or both sides of a rigid substrate coated with a magnetic medium, on which data is stored. Data storage devices typically have several platters that are mounted on a common spindle. Each side on which data is stored commonly has an associated read head and a write head, or sometimes a combined read/write head. The platters are rotated rapidly within the data storage device about the spindle, and an actuator moves heads toward or away from the spindle so that data can be written to or read from tracks. A track is a circular path on the magnetic surface of the platters. One way of increasing data storage capacity is to have very narrow tracks and to place heads very close to the surface of the platter, e.g., micrometers (also, “microns”) away. However, because it takes more energy to write data than to read data (e.g., because the magnetic surface of platters must be magnetized to store data), data storage drive manufacturers inserted a buffer track between tracks storing data so that a wider track can be written to than read from. The buffer tracks could be magnetized when tracks on either side of the buffer tracks (“data tracks”) were written to, but read heads would only read from data tracks and ignore buffer tracks. However, buffer tracks decrease available space on platters.
To avoid wasting space on buffer tracks, a technique employed by the industry is shingled magnetic recording (“SMR”). SMR is a technique to increase capacity used in hard disk drive magnetic storage. Although conventional data storage devices as described above record data by writing non-overlapping magnetic tracks parallel to each other, SMR involves writing new tracks that overlap part of the previously written magnetic track, leaving the previously written magnetic track thinner, thereby allowing for higher track density. The SMR tracks partially overlap in a manner similar to roof shingles on a house.
For SMR drives, a disk can include a number of concentric, overlapping tracks on which data is stored on the surface. A number of zones can be defined on a disk, wherein each zone can include a group of tracks. Generally, data is written to sequential physical blocks within a zone (e.g., physical blocks that have monotonically increasing Physical Block Addresses (PBAs)). Once data has been written to a particular physical block within a zone, that physical block is not modified unless the previous physical blocks within the zone are rewritten as well. Thus, to modify the data stored at a particular physical block, data from the entire zone is read from the disk, the data for the appropriate physical block is modified, and the entire zone is written back to the disk (referred to as a “read-modify-write operation”).
Update-in-place filesystems may use static mappings between Logical Block Addresses (LBAs) and PBAs. Thus, when a component (e.g., higher level software) writes data to a particular LBA, the LBA is mapped to a particular PBA and the data stored at that PBA is modified. Because read-modify-write operations are used to modify data stored at particular PBAs, each update to an LBA of an update-in-place filesystem may result in a read-modify-write operation being performed, potentially causing significant performance degradation.